package cn.xkai.exercise.c;

import java.util.PriorityQueue;

/**
 * @description: 数组中的第K个最大元素
 * @author: kaixiang
 * @date: 2022-07-28
 **/
public class Solution110 {
    public int findKthLargest(int[] nums, int k) {
        heapSort2(nums);
        return nums[k - 1];
    }

    /**
     * 堆排序，把根节点放到堆尾，数组不重复
     * 小顶堆，降序
     */
    public void heapSort2(int[] a) {
        // 空数组或只有1个元素的数组不需要进行排序
        if (a.length <= 1) {
            return;
        }
        int len = a.length;
        //构造堆，从最底层叶子节点开始，叶子节点中小的值与父节点交换
        for (int i = len / 2 - 1; i >= 0; i--) {
            headAdjust2(a, len, i);
        }
        //排序，将根节点放在堆尾，然后从根节点重新调整
        for (int i = len - 1; i >= 1; i--) {
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            headAdjust2(a, i, 0);
        }
    }

    /**
     * 构建堆（小顶堆）
     */
    private void headAdjust2(int[] a, int len, int i) {
        int k = i, temp = a[i], index = 2 * k + 1;
        while (index < len) {
            if (index + 1 < len && a[index] > a[index + 1]) {
                index = index + 1;
            }
            if (a[index] > temp) {
                break;
            }
            a[k] = a[index];
            k = index;
            index = 2 * k + 1;
        }
        a[k] = temp;
    }

    public int findKthLargestQueue(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int n : nums) {
            pq.offer(n);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        return pq.poll();
    }

    public void quickSort(int[] a) {
        // 空数组或只有1个元素的数组不需要进行排序
        if (a.length <= 1) {
            return;
        }
        // 每次i循环增加后，赋值给j，这里写到了for里面
        for (int i = 0, j = i; i < a.length - 1; j = ++i) {
            int ai = a[i + 1];
            // 用下一个值为基准依次向前作比较，如果大于就进行交换
            while (a[j] > ai) {
                a[j + 1] = a[j];
                if (j-- == 0) {
                    break;
                }
            }
            a[j + 1] = ai;
        }
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        Solution110 solution110 = new Solution110();
        System.out.println(solution110.findKthLargest(nums, k));
    }
}
